package com.duoduo.sort;

/**
 * @author dl.chai
 * @version 1.0
 * @description: 快排
 * @date 2023/3/22 21:03
 */

public class 快速排序 {
    public static void main(String[] args) {
        int[] arr = new int[]{6,3,8,9,1,4,5,7};
        int[] quicksort = quicksort(arr, 0, arr.length - 1);
        PrintArray.print(quicksort);
    }

    public static int[] quicksort(int[] arr, int start, int end) {
       if (arr.length<1 || start<0 || end>= arr.length|| start>end){
           return null;
       }
       int zoneIndex=partition(arr,start,end);
       if (start<zoneIndex){
           quicksort(arr,start,zoneIndex);
       }
       if (zoneIndex<end){
           quicksort(arr,zoneIndex+1,end);
       }
       return arr;
    }

    private static int partition(int[] arr, int start, int end) {
        if (start==end){
            return start;
        }
        //选取随机数
        // int pivot = (int) (start + Math.random() * (end - start + 1));
        int pivot = start;
        //zoneIndex 分区指示器
        int zoneIndex = start - 1;
        //交换基准数和最后一个元素的位置
        swap(arr,pivot,end);
        for(int i=start; i <= end; i++){
            if (arr[i]<=arr[end]){
                zoneIndex++;
                if (i > zoneIndex) {
                    swap(arr, i, zoneIndex);
                }
            }
        }
        return zoneIndex;
    }

    private static void swap(int[] arr, int random, int end) {
        int tmp=arr[random];
        arr[random]=arr[end];
        arr[end]=tmp;
    }

}
